class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null && strs.length == 0) {
            return "";
        }
        int minLength = Integer.MAX_VALUE;
        for (int i = 0; i < strs.length; i++) {
            minLength = Math.min(minLength, strs[i].length());
        }
        int l = 0, r = minLength;
        String ans = "";
        while (l < r) {
            int mid = l + ((r - l + 1) >> 1);
            String substring = strs[0].substring(0, mid);
            if (isCommonPrefix(strs, substring)) {
                l = mid;
                ans = substring;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }

    public boolean isCommonPrefix(String[] strs, String prefix) {
        for (String str : strs) {
            if (!str.startsWith(prefix)) {
                return false;
            }
        }
        return true;
    }
}